The present invent ion relates to the methods, systems and devices designed to prove the authenticity of an entity and/or the integrity and/or authenticity of a message.
The patent EP 0 311 470 B1, whose inventors are Louis Guillou and Jean-Jacques Quisquater, describes such a method. Hereinafter, reference shall be made to their work by the terms “GQ patent” or “GQ method”. Hereinafter, the expression “GQ2”, or “GQ2 invention” or “GQ2 technology” shall be used to describe the present invention.
According to the GQ method, an entity known as a “trusted authority” assigns an identity to each entity called a “witness” and computes its RSA signature. In a customizing process, the trusted authority gives the witness an identity and signature. Thereafter, the witness declares the following: “Here is my identity; I know its RSA signature”. The witness proves that he knows the RSA signature of his identity without revealing it. Through the RSA public identification key distributed by the trusted authority, an entity known as a “controller” ascertains, without obtaining knowledge thereof, that the RSA signature corresponds to the declared identity. The mechanisms using the GQ method run “without transfer of knowledge”. According to the GQ method, the witness does not know the RSA private key with which the trusted authority signs a large number of identities.
The GQ technology described above makes use of RSA technology. However, whereas RSA technology truly depends on the factorization of the modulus n, this dependence is not an equivalence, indeed far from it, as can be seen in what are called “multiplicative attacks” against the various standards of digital signatures implementing RSA technology.
The goal of the GQ2 technology is twofold: on the one hand, to improve the performance characteristics of RSA technology and, on the other hand, to avert the problems inherent in RSA technology. Knowledge of the GQ2 private key is equivalent to knowledge of the factorization of the modulus n. Any attack on the triplets GQ2 leads to factorization of the modulus n: this time there is equivalence. With the GQ2 technology, the work load is reduced both for the signing or self-authenticating entity and for the controller entity. Through a better use of the problem of factorizing in terms of both security and performance, the GQ2 technology averts the drawbacks of RSA technology.
The GQ method implements modulo computations of numbers comprising 512 bits or more. These computations relate to numbers having substantially the same size raised to powers of the order of 216+1. But existing microelectronic infrastructures, especially in the field of bank cards, make use of monolithic self-programmable microprocessors without arithmetical coprocessors. The work load related to the multiple arithmetical applications involved in methods such as the GQ method leads to computation times which, in certain cases, prove to be disadvantageous for consumers using bank cards to pay for their purchases. It may be recalled here that, in seeking to increase the security of payment cards, the banking authorities have raised a problem that is particularly difficult to solve. In fact, two apparently contradictory questions have to be examined: on the one hand, increasing security by using increasingly lengthy and distinct keys for each card while, on the other hand, preventing the work load from leading to excessive computation times for the users. This problem becomes especially acute inasmuch as it is also necessary to take account of the existing infrastructure and the existing microprocessor components.
The GQ2 technology is aimed at providing a solution to this problem while still increasing security.
Method